The present disclosure relates to the field of microprocessor design, and more specifically, to stream based lookahead branch prediction.
Branch prediction is a performance-critical component of a pipelined high frequency microprocessor. It is used to predict the direction (taken vs. not taken) and the target address of each branch instruction. This is beneficial because it allows processing to continue along a branch's predicted path rather than having to wait for the outcome of the branch to be determined. A penalty is incurred if a branch is predicted incorrectly. Pipelined branch predictor takes several cycles to make a prediction.
Traditionally, branch prediction is used to steer the flow of instructions down a processor pipeline along the most likely path of code to be executed within a program. Branch prediction uses historical information to predict whether or not a given branch will be taken or not taken, such as predicting which portion of code included in an IF-THEN-ELSE structure will be executed based on which portion of code was executed in the past. The branch that is expected to be the first taken branch is then fetched and speculatively executed. If it is later determined that the prediction was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the instruction proceeding the branch with the correct branch path, incurring a delay between the branch and the next instruction to be executed.
To accelerate speculative searching and efficiently power up structures, it would be advantageous to predict where a stream ends, where it goes and include information about the next stream. Rather than making a branch prediction for each search, it may also be advantageous to make the prediction based on the start of the data stream, and make one entry per stream rather than one entry per search. It may also be advantageous to identify the most common exit point from a branch prediction stream and uses that exit point as the column prediction, which may achieve even more efficiency for the column predictor, and thus increase performance as branch predictions are accelerated whenever the column predictor is correct.